1. Field of the Invention
The present invention relates to a multiplying circuit used in a CPU, and relates to a microcomputer including such multiplying circuit.
2. Description of the Related Art
A principle of subtraction shift-type-division which performs a subtraction between a dividend or partial remainder by RSD representation and a divisor by twos complement representation is shown in pages 748 to 756 of the IEEE, Journal of Solid-State Circuit, Vol. 25, No. 3 (June, 1990).
A number by RSD (Redundant Signed Digit) representation is a numerical representation which represents the number of each digit by {-1, 0, 1}, and is expressed as Y in the following expression. ##EQU1##
While, a number by twos complement representation is expressed as Z in the following expression. ##EQU2##
The above-mentioned number Y by RSD representation and the number Z by twos complement, representation are added as shown in a schematic diagram of FIG. 1, and their sum S is obtained as a number by RSD representation shown in the following expression. ##EQU3##
In FIG. 1, symbols of large .largecircle. respectively designate full adders, and symbols of small .largecircle. respectively designate inverted inputs to or inverted outputs from the full adders.
FIG. 2(a) is a schematic diagram showing inputs and outputs to and from the full adder shown in FIG. 1, and FIG. 2(b) is a truth table therebetween.
While, the number Y by RSD representation and the number Z by twos complement representation are subtracted as shown in a schematic diagram of FIG. 3, and their difference D is obtained as the number by RSD representation shown in the following expression. ##EQU4##
In FIG. 3, in the same way as FIG. 1, the symbols of large .largecircle. respectively designate the full adders and the symbols of small .largecircle. respectively designate the inverted inputs to or the inverted outputs from the full adders.
Truth tables of the full adders shown in FIG. 3 are similar to that shown in FIG. 2(b).
Such addition and subtraction of the number Y by RSD representation and the number Z by twos complement representation can be performed rapidly because of free from carry propagations.
The Booth algorithm is well known as a multiplication for a high speed multiplying circuit. In the case where a multiplying circuit is realized by the Booth algorithm, there are two techniques. One of them is such that partial products are simultaneously generated, and all of them are statically added. Another is such that partial products are repeatedly added. In the latter, addition and subtraction by abovementioned number by RSD representation and number by twos complement representation can be used. That is, a number by RSD representation is used for partial products and number by twos complement representation is used for multipliers. In addition, a counter is used for counting repetition numbers (multiplication cycles).
The conventional multiplying circuit is constructed as abovementioned, since a counter is used for counting the multiplication cycles, a problem of increasing a number of transistors occurs. Also, when the higher bits of the product obtained as a number with redundant code is converted into binary number, compensation by lower bits of the product is required.